#include <iostream>

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
class Solution {
public:
    Node* treeToDoublyList(Node* root) {

        if(root == nullptr)
            return root;
        Node* leftNode = myTraversal_left(root->left, root);
        Node* rightNode = myTraversal_right(root->right, root);
        leftNode->right = root;
        root->left = leftNode;
        rightNode->left = root;
        root->right = rightNode;
        std::cout<<"infunc "<<leftNode<<std::endl;
        return leftNode;
    }
    Node* myTraversal_left(Node* &root, Node* &parent)
    {
        if(root == nullptr)
            return root;
        Node* leftNode = myTraversal_left(root->left, root);
        Node* rightNode= myTraversal_right(root->right, root);

        if(leftNode != nullptr) root->left = leftNode;
        else rightNode = root;
        if(rightNode != nullptr) root->right = rightNode;
        else root->right = parent;
        return rightNode;
    }
    Node* myTraversal_right(Node* &root, Node* &parent)
    {
        if(root == nullptr)
            return root;

        Node* leftNode = myTraversal_left(root->left, root);
        Node* rightNode= myTraversal_right(root->right, root);
        if(leftNode != nullptr) root->left = leftNode;
        else root->left = parent;
        if(rightNode != nullptr) root->right = rightNode;
        else leftNode = root;
        return leftNode;
    }
};
int main() {
    Node n1(1);
    Node n3(3);
    Node n2(2,&n1,&n3);
    Node n5(5);
    Node n4(4,&n2,&n5);
    std::cout<<&n3<<" "<<&n4<<" "<<&n5<<std::endl;
    Solution sol;
    Node* result =sol.treeToDoublyList(&n4);
    std::cout<<"outfunc "<<result<<std::endl;

    for(int i = 0; i<3 ;i++) {
        std::cout << result << " ";
        result = result->right;
    }
//    std::cout << "Hello, World!" << result->val<<std::endl;
    return 0;
}
